1. Field of the Invention
The present invention relates to the field of computing and more particularly to quantum computing.
2. Description of the Background
In electronic circuits a gate is a digital logic operation embodied in a circuit having at least one digital input, or bit, and having one digital output, or bit, wherein the circuit generates a value of the output that depends upon the values of the inputs. The gate references the manipulation of the input bits to generate the value of the output bit. Measures of circuit efficiencies include speed of performing their operation and number of gates required to perform their operation.
The input size of a circuit means the number of bits that are in the input. The most common circuit input measurements are the depth of the circuit and the size of the circuit. The depth of the circuit relates to the highest number of gates that must be traversed by a signal before an answer is computed. The size of a circuit is the total number of gates in the whole circuit. For example, a circuit that computes simple addition of 2 n-bit binary integers has input size of 2n. These values as functions allow predicting the size of a circuit as the input size varies.
If a function that expresses the size of a circuit for computing a specified computation grows very quickly as the input size increases then that computation problem is only efficiently solvable for small inputs. Thus when comparing sizes of circuits as expressed by a function of the input size one compares their asymptotic growth, that is their growth as the input size approaches infinity.
A circuit has polynomial size if the circuit has a size that is expressed as a polynomial of the input size. A circuit has logarithmic depth if the depth of the circuit is expressed as a logarithm of the input size. A special notation, called big-Oh (“O”) notation, is used to express functions, and thus circuit sizes or depths, in a way that only expresses the class of the function. For example, O(n2) is the class of functions whose size increases polynomially with increasing input size no faster than some constant coefficient times n2. This notation is more specific than just claiming polynomial size. Generally a circuit is considered efficient if it has polynomial size. In the current Invention, the primary concern is the depth of a circuit. The terminology of an efficient circuit here generally refers to the fact that its depth is either logarithmic or poly-logarithmic.
The same notations for describing circuit efficiency are used to describe the probability of error of a given circuit. The probability of error of a circuit may be expressed as a function of the circuit's input size. Probability of a circuit producing an error is denoted by an epsilon, ε. Exponentially small probability of error means that the probability of error is 1/f(n), where f(n) is in O(2n). Probability of error is 1/f(n), in a circuit design, is generally considered to be acceptable because errors caused by circuit malfunction or other problems exist with higher probabilities than this probability.
Quantum computation or quantum information processing (QIP) has developed methods for using quantum information for computing. Quantum states are denoted with the ket symbol and written in the form |x> where x represents a quantum wave function. A superposition defining a single qubit's state is written |x>=α|0>+β|1> where alpha and beta are complex number weighting coefficients. The sum alpha squared plus beta squared is normalized to one so that the probability of the observable quantity associated with |x> is one.
A problem implementing quantum circuits is data loss due to interaction of qubits with particles in the environment causing changes in the qubit's quantum mechanical state. The loss of qubit data due to interaction with the environment is named decoherance. Generally applicable methods for combatting decoherence exist. For instance, implementing quantum error correcting codes or decoherence free subsystems may reduce decoherence.
The present inventors recognized that minimizing depth of quantum circuits may speed up computation and reduce data loss by reducing time qubits in the circuit are exposed to interaction with the environment since increasing quantum circuit depth increases quantum computing time. Thus, the present inventors recognized that logarithmic or poly-logarithmnic depth circuits offer a great advantage over polynomial depth circuits. In classical computing, it is important to define what physical states correspond to a “0” or a “1” in a mathematical computation. Similarly, in quantum computing, it is important to define a computational basis. For a single qubit, the states |0> and |1>, representing the number 0 and 1 respectively. For n qubits, the computational basis is simply defined as the tensor product space of the individual qubits of the 2n possibilities from |00 . . . 0>, |00 . . . 1>, |00 . . . 10> to |11111>. For simplicity, when discussing an n-qubit register as a single entity, it is common to simply refer to the state of all zeroes |00 . . . 0> as |0>.
Certain quantum computing mathematical operations, also called gates, are much like logical gates AND and NOT classical computing functions. Common quantum computing gates include the Hadamard gate. The Hadamard gate acts on a single qubit. The Hadamard gate converts the qubit state
                            0            〉        ⁢                  ⁢          to        ⁢                  ⁢          1              2              ⁢                          0            〉        +                    1                  2                    ⁢                      1              〉  and converts the qubitstate
                            1            〉        ⁢                  ⁢          to        ⁢                  ⁢          1              2              ⁢                          0            〉        -                              1                      2                          ⁢                            1                    〉        .  Another common gate is the quantum controlled-NOT gate, which acts in some ways as the classical XOR. The quantum controlled-NOT gate acts on two qubits, a control qubit and a qubit to be negated. If the control qubit is in state |1> then the second qubit is negated, otherwise nothing occurs. If the second qubit is initially |0>, then this gate will XOR the state of the control qubit onto the second bit.
Another common two-qubit gate is the controlled phase shift gate, sometimes referred to as “the controlled θ” gate. The controlled θ gate maps |x>|y> to eiθxy |x>|y>.
All quantum computing operations ma) be composed of combinations of quantum one bit gates and quantum two bit controlled-NOT gates, and those gates have been realized in physical systems, such as quantum computing NMR systems.
The discrete Fourier transformation is referred to herein after as DFT. DFT is a mathematical mapping from one finite set of complex numbers to another set of complex numbers of similar size. DFT is defined by the following equation for two sets of complex numbers (α0, α1, . . . αm−1), and (β0,β1, . . . βm−1) where
      β    x    =            1              m              ⁢                  ∑                  y          =          0                          m          -          1                    ⁢                                    (                          ⅇ                              2                ⁢                                  Ih                  /                  m                                                      )                                x            ·            y                          ⁢                  α          y                    DFT can be computed with depth O(m log m) by the fast Fourier transform. DFT has many useful applications because of its computational efficiency expressed by its low order depth. The efficiency of the DFT is one of the most important algorithms in classical computing.
Application of the DFT to transform the amplitudes of particular qubits or collections of qubits in quantum circuits is called the Quantum Fourier Transformation, referred to herein after as the QFT. Current methods for performing exact or approximate QFT on n qubits have polynomial depth.
QFT already has many applications in quantum computing, such as algorithms of Shor to efficiently compute discrete logarithms and factor numbers. See Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer” SIAM Journal of Computing, Volume 26, Number 5, pages 1484–1509 (1997) and D. Boneh and R. J. Lipton, “Advances in Cryptology: Proceedings of Crypto'95”, Lecture Notes in Computer Science, Vol., 963, 424 (1995). Current RSA cryptography systems make use of the assumption that factoring large numbers is generally a computationally time intensive task for large integers. Shor's algorithm contravenes that assumption. Therefore, current cryptography systems are no longer secure.
A computational basis state of size n is defined to be a state |x> representing an arbitrary n-bit binary number.
A Fourier basis state for a computational basis state is the QFT of the computational basis state. Thus, the |Px> is the QFT of the computational basis state |x>, which means that |Px> is the result of applying the QFT to |x>.
The paper, Cleve and Watrous, “Fast parallel circuits for the quantum Fourier transform” in Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS '00), pages 526–536 (2000), is incorporated herein by reference. Universal quantum gates and universal quantum computers are disclosed in “Elementary gates for quantum computation” Barenco, Bennett, Cleve, DiVincenzo, Margolus, Shor, Sleator, Smolin, and Weinfurter, Physical Review A, Volume 52, Number 5, pages 3457–3467 (1995), which is incorporated herein by reference. Quantum gates designed to avoid erroneous data caused by decoherence are disclosed in Gottesman, “Stabilizer Codes and Quantum Error Correction” http://xxx.lanl.gov/abs/quant-ph/9705052, which is incorporated herein by reference.
Quantum computing with local gates and models for scaling quantum computing are disclosed in Fault-Tolerant Quantum Computation with Local Gates”, D. Gottesman http://xxx.lanl.gov/abs/quant-ph/9903099 and “Efficient Linear Optics Quantum Computation” by Knill, Laflamme and Milburn, http://xxx.lanl.gov/abs/quant-ph/0006088, Braunstein and Lo, “Scalable Quantum Computers” (2000), which are incorporated herein by reference.
The quantum operations defined herein below are physical operations performed on quantum states of the qubits defining a data processing component of a quantum computing circuit. Quantum computing circuits include sets of universal quantum gates. A universal quantum gate is a fundamental logical building block from which any quantum circuit can be embodied. Universal quantum gates have been successfully implemented in a 7 qubit quantum computer to factor the number 15. That computer employed nuclear spin ½ moments as qubits, and employed nuclear magnetic resonance technology to perform operations on those qubits analogous to classical gates to factor the number 15.